// Package day_10_KMP_manacher base_kmp
// @Title day_10_KMP_manacher
// @Description  KMP算法
// @Author  == 琳琳也叫王木木 ==  2021/9/3 14:51
// @Create  2021/9/3 14:51
package day_10_KMP_manacher

import "fmt"

func GetIndexOf(s, m string) int {
	if s == "" || m == "" || len(m) < 1 || len(s) < len(m) {
		return -1
	}
	i1, i2 := 0, 0             // i1 在主串中的位置， i2在模式串的指针位置
	nextArr := getNextArray(m) // next数组
	fmt.Println(nextArr)
	for i1 < len(s) && i2 < len(m) { // 都不越界
		if s[i1] == m[i2] { // 相等，双指针同时往后移动
			i1++
			i2++
		} else if nextArr[i2] == -1 { // -1 代表什么 ？ i2 来到了0位置 发现和i1也配不上，i1指针后移
			i1++
		} else {
			i2 = nextArr[i2]
		}
	}
	if i2 == len(m) {
		return i1 - i2
	}
	return -1
}

func getNextArray(s string) []int {
	if len(s) == 1 {
		return []int{-1}
	}
	next := make([]int, len(s))
	next[0] = -1
	next[1] = 0
	cn := 0
	i := 2
	for i < len(next) {
		if s[i-1] == s[cn] {
			next[i] = cn + 1
			cn++
			i++
			//next[i++] = ++cn
		} else if cn > 0 {
			cn = next[cn]
		} else {
			next[i] = 0
			i++
		}
	}
	return next
}
